#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int movingCount(int m, int n, int k);
int check(int x);

int main()
{
	return 0;
}

int movingCount(int m, int n, int k)
{
	if (!k) return -1;
	char vis[m][n]; memset(vis, 0, sizeof(vis));

	int res = 1;
	vis[0][0] = 1;
	for (int j = 1; j < n; j++) {
		vis[0][j] |= vis[0][j - 1];
		res += vis[0][j];
	}
	for (int i = 1; i < m; i++) {
		res += vis[i][0];
		for (int j = 1; j < n; j++) {
			if (check(i) + check(j) > k) continue;
			vis[i][j] |= vis[i - 1][j];
			vis[i][j] |= vis[i][j - 1];
			res += vis[i][j];
		}
	}

	return res;
}

int check(int x)
{
	int res = 0;
	for (; x; x /= 10)
		res += x % 10;
	return res;
}
